1. Field of the Invention
The invention relates generally to ordering events in a computing system and more particularly to maintaining the completion order of events in a computer system.
2. Description of the Relevant Art
As processors and computing subsystems get faster and faster (and more complicated), "implicit ordering requirements" are being discovered between events that occur during the operation of a computer. These ordering requirements can be thought of as a detailed contract between hardware designers and software writers that goes beyond the instruction set of a computer and the "memory model".
A memory model is a recently well-documented contractual statement that varies amongst computer systems and states how the completion of loads and stores are guaranteed. In high performance systems they don't complete in the order written in a program.
These ordering requirements sometimes weren't explicitly described or required by prior hardware/software systems, only because either communication delays were balanced for all events, or the events were serialized by a single communications medium, or the interesting events never occurred in parallel. Therefore, failures due to improper ordering or re-ordering never occurred.
An example is an I/O subsystem, e.g., a disk drive, that has the ability to write data to main memory on its own, independent of the processor. This kind of subsystem is activated by code running on the processor and, after the write to main memory is finished, the processor's software needs to be notified, usually by an interrupt.
In systems with complicated memory systems, the subsystem may believe it has completed all its writes, when, in fact, the writes are still not all the way in the main memory, i.e., the write data is still in temporary buffers. This is because there usually isn't an acknowledge back from the final destination (main memory) to the subsystem for a variety of implementation reasons.
If the interrupt path to the processor is direct enough, the processor may receive the interrupt signifying completion and try to read the new data from main memory before it is actually there. This would be an error, since the software assumes it should be there.
PCI, the industry-standard Peripheral Component Interface, doesn't specify the ordering of interrupts or a transmission mechanism to the processor. Therefore, some modern operating systems, which assume this interrupt/prior write ordering, need a mechanism to guaranty it.
Bus Bridges, which isolate bus segments electrically, usually have buffers that accumulate the data for reads and writes temporarily delaying the transmission and completion of memory transaction initiated by a computing subsystem. Since the interrupts are usually transmitted through a means independent of the bus bridge, the interrupts typically arrive at the processor quickly. Thus, the bus bridges exacerbate the interrupt/prior write completion problem.
As set forth in the PCI specification, ordering is maintained by a system of buffer-flushing. According to the specification, a read transaction must push ahead of it through the bridge any posted writes originating on the same side of the bridge and posted before the read. Before the read transaction can complete on its originating bus, it must pull out of the bridge any posted writes that originated on the opposite side of the bridge and were posted before the read command completes on the read-destination bus.
For example, a common situation is the writing of data to a cache and writing a cache invalidation flag. Typically, an interrupt will signal the completion of both writes. However, the writes could be posted to the bridge buffers and may not reside at the cache and invalidation flag. Accordingly, if the CPU issues a cache read command, both writes are pulled out of the bridge buffers before the CPU read command completes.
The mechanism of buffer-flushing can lead to deadlocks and is not necessary for all read operations.